import java.util.Arrays;

/**
 * 1584. 连接所有点的最小费用
 * https://leetcode-cn.com/problems/min-cost-to-connect-all-points/
 * 其他解法：并查集
 */
public class Solutions_1584 {
    public static void main(String[] args) {
        int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};  // output: 20
//        int[][] points = {{3, 12}, {-2, 5}, {-4, 1}};  // output: 18
//        int[][] points = {{0, 0}, {1, 1}, {1, 0}, {-1, 1}};  // output: 4
//        int[][] points = {{-1000000, -1000000}, {1000000, 1000000}};  // output: 4000000
//        int[][] points = {{0, 0}};  // output: 0

        int result = minCostConnectPoints(points);
        System.out.println(result);
    }

    /**
     * 模拟法
     * 1. 默认从第一个坐标 A 开始（将坐标 A 标记为已访问，与其他未访问坐标比较距离）寻找全部坐标中，离的最近的点
     *      寻找过程中，同时将每个坐标与当前坐标的距离计算出来，记录到 distant 数组中
     * 2. 寻找过程中，比较并保存下与 A 最近的点，即距离最短的。
     * 3. 若有 B 点与 A 点的距离最近，那么 A 点与 B 点之前就可以连线
     * 4. 将 B 点标记为已访问，将 B 点与其他未访问的坐标比较距离（即找到可以连线的最近的点），重复第一步骤即可。
     */
    public static int minCostConnectPoints(int[][] points) {
        int res = 0;
        int len = points.length;
        int index = 1;
        // visited[0] = true：表示 points[0] 点已经连接了最近的点
        boolean[] visited = new boolean[len];

        // 第一个点为默认查询点，同时标记为已访问
        int curX = points[0][0];
        int curY = points[0][1];
        visited[0] = true;

        int[] minDistance = new int[len];
        Arrays.fill(minDistance, Integer.MAX_VALUE);

        while (index < len) {
            // 定义与 [curX, curY] 坐标最近连接的坐标在 points 中的索引，及之间的距离
            int next = -1, min = Integer.MAX_VALUE;
            for (int i = 0; i < len; i++) {
                if (visited[i]) {
                    // points[i] 点已经连线过
                    continue;
                }
                // 将 [curX, curY] 与可进行连接的点，进行距离计算，更新与可连接点的最短连接距离
                // 在可进行连接的点中，与 [curX, curY] 最小距离的即是可以与其连接的点
                minDistance[i] = Math.min(minDistance[i], Math.abs(points[i][0] - curX) + Math.abs(points[i][1] - curY));
                if (minDistance[i] < min) {
                    min = minDistance[i];
                    next = i;
                }
            }
            // [curX, curY] 可以与 points[next] 点进行连接，得到最小的连接边长
            // points[next] 成为新的查询点，继续与其他可进行连接的点（未访问，未连接过的点）比较
            curX = points[next][0];
            curY = points[next][1];
            // 标记为已访问
            visited[next] = true;
            // 最小连接边长加入总和
            res += min;
            index ++;
        }
        return res;
    }
}
